﻿using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace BFS
{
    class Program
    {
        static int iSoDinh;
        static int iDau;
        static int iCuoi;
        static int[][] matrix = new int[100][];
        static int[] arrDanhDau = new int[iSoDinh];

        static void Main(string[] args)
        {
            docFile("input.txt");
            xuat();
            runBFS();
            Console.Read();
            
        }
        static void runBFS()
        {
           //int[] arrDanhDau = new int[iSoDinh];
            int[] Vk = new int[iSoDinh];
            int[] Vk1 = new int[iSoDinh];
            int iSPTVk = 1;
            int iSPTVk1 = 0;
            khoitaomangdanhdau(ref arrDanhDau);
            Vk[0] = iDau;
            arrDanhDau[0] = 0;
            int k = 0;
            while(kiemtraDichtrongVk(Vk,iSPTVk)==false&&iSPTVk!=0)
            {
                iSPTVk1=0;
                TaoVk1(Vk,iSPTVk,ref Vk1,ref iSPTVk1);
                chepVk1ChoVk(ref Vk,ref iSPTVk, Vk1,iSPTVk1);
            }
            if(iSPTVk==0)//Vk rỗng
            {
                Console.WriteLine("Bi Duong");
            }
            else//quay lui
            {
                string sDuongDi = "--->" + iCuoi;
                int iDinhDangLui = iCuoi;
                while (iDinhDangLui != iDau)//Gặp đầu thì dừng
                {
                    sDuongDi = "---->" + arrDanhDau[iDinhDangLui] + sDuongDi;
                    iDinhDangLui = arrDanhDau[iDinhDangLui];//Đỉnh trước hiện tại bằng đỉnh lui tiếp theo
                }
                Console.WriteLine(sDuongDi);
            }
        }
        static void chepVk1ChoVk(ref int[] Vk,ref int iSPTVk, int [] Vk1, int iSPTVk1)
        {
            iSPTVk=0;
            for(int i=0;i<iSPTVk1;i++)
            {
                Vk[iSPTVk]=Vk1[i];
                iSPTVk++;
            }
        }
        static void TaoVk1(int[] Vk,int iSPTVk, ref int [] Vk1, ref int iSPTVk1)
        {

            iSPTVk1=0;
            for(int i=0; i<iSPTVk;i++)
            {
                //duyet don thứ Vk[i] trong ma tran
                for(int j=0; j<iSoDinh ;j++)
                {
                    if(matrix[Vk[i]][j]==1 && arrDanhDau[j]==-1) //kiểm tra đỉnh i có dính với đỉnh Vk[i] ko?
                    {
                        //thêm vào Vk[1]
                        Vk1[iSPTVk1] = j;
                        iSPTVk1++;
                        arrDanhDau[j] = Vk[i];// gán đỉnh trước j là VK[i]
                    }
                }
            }
        }
        static bool kiemtraDichtrongVk(int[] Vk,int iSoPT)
        {
            for(int i = 0; i<iSoPT;i++)
            {
                if(Vk[i]==iCuoi)
                {
                    return true;
                }
            }
            return false;
        }
        static void khoitaomangdanhdau(ref int[] arrDanhDau)
        {
            arrDanhDau = new int[iSoDinh];
            for (int i = 0; i < iSoDinh; i++)
            {
                arrDanhDau[i] = -1;
            }
        }
        static void docFile(string sFileName)
        {
            StreamReader file = new StreamReader("input1.txt");
            string sLine = file.ReadLine();
            iSoDinh = Convert.ToInt32(sLine.Split(' ')[0]);
            iDau = Convert.ToInt32(sLine.Split(' ')[1]);
            iCuoi = Convert.ToInt32(sLine.Split(' ')[2]);
            for(int i = 0; i < iSoDinh; i++)
            {
                sLine = file.ReadLine();
                string [] arrDong = sLine.Split(' ');
                matrix[i] = new int[iSoDinh];
                for(int j = 0; j < iSoDinh; j++)
                {
                    matrix[i][j] = Convert.ToInt32(arrDong[j]);

                }
            }

        }
        static void xuat()
        {
            for (int i = 0; i < iSoDinh; i++)
            {
                for (int j = 0; j < iSoDinh; j++)
                {
                    Console.Write(matrix[i][j].ToString());
                }
                Console.WriteLine();
            }
        }
    }
}
